/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Practica7.Practica;

import Practica7.graphs.Dijkstra;
import Practica7.util.Graph;
import Practica7.util.Vertex;
import java.util.Comparator;
import java.util.List;

/**
 *
 * @author miguel
 */
public class MyDijkstra implements Dijkstra{

    @Override
    public Graph getDijkstra(Graph graph, Vertex vertex) {
        MyGraph g = (MyGraph)graph;
        MyBinomialQueue<MyVertex> mbq = new MyBinomialQueue<>(new CompareVertex());
        for(MyVertex v: (List<MyVertex>)g.getVertexList()){
            v.setDistancia(Integer.MAX_VALUE);
            v.setPadre(null);
        }
        
        MyVertex inicial = (MyVertex)g.getVertex(vertex.getIndex());
        inicial.setDistancia(0);
        mbq.insert(inicial);
        while(!mbq.isEmpty()){
            MyVertex u = mbq.deleteMin();
            if(u.getDistancia() == Integer.MAX_VALUE){
                break;
            }
            for(MyVertex v: (List<MyVertex>)u.getNeighboursList()){
                int alt = u.getDistancia()+g.getWeight(u, v);
                if(v.getDistancia()>alt){
                    v.setDistancia(alt);
                    v.setPadre(u);
                    mbq.insert(v);
                }
            }
            
        }
        
        MyGraph g1 = new MyGraph();
        for(MyVertex v: (List<MyVertex>)g.getVertexList()){
            g1.getVertexList().add(v);
        }
        for(MyEdge e: (List<MyEdge>)g.getEdgesList()){
            if(((MyVertex)e.getTarget()).getPadre().equals((MyVertex)e.getSource()) ||((MyVertex)e.getSource()).getPadre().equals((MyVertex)e.getTarget()) ){
                g1.getEdgesList().add(e);
            }
        }
        
        
        
        return (Graph) g1;
    }
    
    
    class CompareVertex implements Comparator<MyVertex> {

        @Override
        public int compare(MyVertex o1, MyVertex o2) {
            return o1.getDistancia() > o2.getDistancia() ? 1 : (o1.getDistancia() == o2.getDistancia() ? 0 : -1);
        }
    }
    
}
